package Test;

public class Test03 {
//    public int numSquares(int n)
//    {
//        int[] dp = new int[n + 1];
//        dp[1] = 1; // 初始化
//        for(int i = 2; i <= n; i++) // 枚举每个数
//        {
//            dp[i] = 1 + dp[i - 1]; // ⾄少等于 1 + dp[i - 1]
//            for(int j = 2; j * j <= i; j++) // ⽤⼩于 i 的完全平⽅数划分区间
//                dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // 拿到所有划分区间内的
//        }
//        // 返回结果
//        return dp[n];
//    }




    public int change(int amount, int[] coins)
    {
        // 空间优化
        int[] dp = new int[amount + 1]; // 建表
        dp[0] = 1; // 初始化
        for(int x : coins) // 拿出物品
            for(int j = x; j <= amount; j++) // 注意遍历顺序和起始终⽌位置
                dp[j] += dp[j - x];
        return dp[amount];
    }
    public int coinChange(int[] coins, int amount)
    {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int n = coins.length, INF = 0x3f3f3f3f;
        int[] dp = new int[amount + 1];
        for(int j = 1; j <= amount; j++) dp[j] = INF;
        for(int i = 1; i <= n; i++)
            for(int j = coins[i - 1]; j <= amount; j++)
                dp[j] = Math.min(dp[j], dp[j - coins[i - 1]] + 1);
        return dp[amount] >= INF ? -1 : dp[amount];
    }
    public int lastStoneWeightII(int[] stones)
 {
         int n = stones.length, sum = 0;
         for(int x : stones) sum += x;
         int m = sum / 2;
         int[] dp = new int[m + 1];
         for(int i = 1; i <= n; i++)
             for(int j = m; j >= stones[i - 1]; j--) // 注意修改遍历顺序
             dp[j] = Math.max(dp[j], dp[j - stones[i - 1]] + stones[i - 1]);
         return sum - 2 * dp[m];
         }
    public int lastStoneWeightII1(int[] stones)
    {
        int n = stones.length, sum = 0;
        for(int x : stones) sum += x;
        int m = sum / 2;
        int[][] dp = new int[n + 1][m + 1];
        for(int i = 1; i <= n; i++)
            for(int j = 0; j <= m; j++)
            {
                dp[i][j] = dp[i - 1][j];
                if(j >= stones[i - 1])
                   dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - stones[i - 1]] + stones[i-1]);
            }
        return sum - 2 * dp[n][m];
    }
    public int findTargetSumWays(int[] nums, int target)
 {
         int n = nums.length, sum = 0;
         for(int x : nums) sum += x;
         int aim = (sum + target) / 2;
         // 处理⼀下边界情况
        if(aim < 0 || (sum + target) % 2 == 1) return 0;

         int[][] dp = new int[n + 1][aim + 1];
         dp[0][0] = 1;
         for(int i = 1; i <= n; i++)
             for(int j = 0; j <= aim; j++)
         {
             dp[i][j] = dp[i - 1][j];
             if(j >= nums[i - 1])
                 dp[i][j] += dp[i - 1][j - nums[i - 1]];
             }
         return dp[n][aim];
         }
}
